有句話是 「programming = data structures + algorithms」，一個好的程式碼需要好的資料結構與演算法，而演算法最看重的就是複雜度，複雜度越小，程式碼就越有效率。

Algorithm

簡而言之，演算法是用來解決問題的，而最常見的做法就是將一個大問題分解成好多個小問題，並解決這些子問題，而這樣的方式稱作遞迴 (recursion)。

此外，演算法中強調了兩種複雜度，分別為空間複雜度(space complexity)與時間複雜度(time complexity)，在大部分的情況，時間複雜度比空間複雜度來得更重要。

Recursion

我們最常見的遞迴做法就是寫一個函數並不斷重複使用。
在河內塔(Hanoi tower)的例子中，應用遞迴是一個非常 clever 的做法，不過，並不是萬靈丹，相信大家對Fibonacci數列都不陌生，就是 1, 1, 2, 3, 5, 8, 13, 21,...，從第三個數開始，每一項都是前兩項的和，我們可以分別比較 recursion、repetitive 的做法：

Recursion

fib(n-1) + fib(n-2)

Repetitive

int fib1 = 1, fib2 = 1;
for (int i = 2; i < n; i++) {
	fib3 = fib1 + fib2
	fib1 = fib2	
	fib2 = fib3
}

在這樣的情況下，選擇 repetitive 的做法會比 recursion 來得更好，因為 repetitive 會花費的時間是 polynomial time，也就是說其所需要跑 次 （C1為ㄧ定值），而 recursive 則是算 exponential time，也就是他會跑 次（C2為一定值）。因此，當 n 大到一定程度時， 會大於 。

Searching

Search 是一個非常常見的遞迴應用。

假設我們現在有一個陣列Ａ以及一整數 p，我們想要知道 p 是否在於Ａ，而且這個陣列 A 是沒有排序過的陣列，一個最直觀的方法就是 linear search，就是從Ａ的第一項開始判斷，從頭開始一個一個的找，這個方法簡單明瞭，不過呢，有的時候可能會有點沒效率，如果今天我們這個陣列是已經排序好了，使用 binary search 可能更好。

Binary search
首先，我們先跟中位數 m 做比較，這時候我們有三種情況：

1. p = m：Bingo！
2. p < m：這時候我們知道如果 p 存在，就一定會在這個陣列的前半部。
3. p > m：這時候我們知道如果 p 存在，就一定會在這個陣列的後半部。

接著我們可以寫一個函數

binarySearch (a sorted array A, search in between from and to, search for p)
	if n = 1
		return true if Afrom = p; return false otherwise
	else
		let median be floor((from + to) / 2)
		if p = Amedian
			return true
		else if p < Amedian
			return binarySearch(A, from, median, p)
		else
			return binarySearch(A, median + 1, to, p)

Binary search 可以讓我們的效率大幅提升，我們只需要跑 次！

Sorting

有兩種sorting的方式：insertion sort & merge sort。

Insertion sort

insertionSort(a non-repetitive array A, the array length n, an index cutoff < n)
// at any time, A1..cutoff is sorted and A(cutoff + 1)..n is unsorted

	if Acutoff + 1 < A1..cutoff
		let p be 1
	else
		find p such that Ap – 1 < Acutoff + 1 < Ap
		insert Acutoff + 1 to Ap
		and shift Ap..cutoff to A(p + 1)..(cutoff + 1)

	if cutoff + 1 < n
		insertionSort(A, n, cutoff + 1)

Merge sort

Merge sort 就是將一個排列好的陣列插入另一個排列好的陣列。

首先要先開一個跟總數一樣大的陣列，接下來：

mergeSort(an array A, the array length n)
	let median be floor((1 + n) / 2)
	mergeSort(A1..median, median) 
	// now A1..median is sorted
	mergeSort(A(median + 1)..n, n – median + 1) 
	// now A(median + 1)..n is sorted

	merge A1..median and A(median + 1)..n

以上就是今天的內容！